package Zhan;

public class SeqStack implements IStack {
    public static final int DEFAULT_SIZE = 8;
    public Object[] elements; // 顺序栈存储空间
    public int top; // 指向栈顶元素的指针
    public int maxSize; // 栈的最大存储单元个数

    // 构造最大存储单元个数为maxSize的空栈
    public SeqStack() {
        this(DEFAULT_SIZE); // 创建最大容量为DEFAULT_SIZE栈
    }

    // 构造最大存储单元个数为maxSize的空栈
    public SeqStack(int maxSize) {
        top = -1; // 空栈
        this.maxSize = maxSize;
        elements = new Object[maxSize];
    }

    // 输出栈中的所有数据元素
    public void display() {
        if (top == -1) {
            System.out.println("栈为空");
        } else {
            for (int i = top; i >= 0; i--) {
                System.out.print(this.elements[i] + " ");
            }
            System.out.println();
        }
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return this.top < 0;
    }

    // 返回栈中数据元素个数
    public int length() {
        return this.top + 1;
    }

    // 返回栈顶元素
    public Object peek() {
        // 如果栈为空则抛出异常
        if (isEmpty()) {
            throw new StackEmptyException("错误，栈为空。");
        }
        return elements[this.top];
    }

    // 入栈
//	  public void push(Object x) throws Exception {
//	  elements[++top] = x;
//	   }

    public void push(Object x) throws Exception {
        // 如果当前栈的元素个数超过了栈的最大容量
        if (this.maxSize <= length()) {
            // 就调用扩容方法
            expandSpace();
        }
        /*
         * 将传入的元素放入栈顶， 先将游针top自增，然后将元素放入新的栈顶
         */
        elements[++top] = x;
    }

    // 扩容方法
    private void expandSpace() {
        // 创建一个新的数组长度为现有元素个数的两倍
        Object[] a = new Object[length() * 2];
        // 将原数组的元素copy到新数组中去
        for (int i = 0; i < length(); i++) {
            a[i] = elements[i];
        }
        // elements和a都是引用类型变量
        // 它们分别存储对象（在这里是数组对象）在内存中的地址
        // 所以应该是将原数组引用指向新数组(不是将a赋值给elements)，实现栈的扩容
        elements = a;
    }

    // 出栈
    public Object pop() throws StackEmptyException {
        // 如果栈为空则抛出异常
        if (isEmpty()) {
            throw new StackEmptyException("错误，栈为空。");
        }
        // 获取出栈的元素
        Object obj = elements[this.top];
        // 将栈顶元素设置为空，并将top指针减1
        elements[this.top--] = null;
        // 返回出栈的元素
        return obj;
    }

}
